{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Time to Kill All Monsters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #dynamic-programming #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #动态规划 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumTime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #杀死所有怪物的最短时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你有一个整数数组 <code>power</code>，其中&nbsp; <code>power[i]</code> 是第 <code>i</code> 个怪物的力量。</p>\n",
    "\n",
    "<p>你从 <code>0</code> 点法力值开始，每天获取&nbsp;<code>gain</code> 点法力值，最初 <code>gain</code> 等于 <code>1</code>。</p>\n",
    "\n",
    "<p>每天，在获得 <code>gain</code>&nbsp;点法力值后，如果你的法力值大于或等于怪物的力量，你就可以打败怪物。当你打败怪物时:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>\n",
    "\t<p data-group=\"1-1\">你的法力值会被重置为 <code>0</code>，并且</p>\n",
    "\t</li>\n",
    "\t<li>\n",
    "\t<p data-group=\"1-1\"><code>gain</code>&nbsp;的值增加 <code>1</code>。</p>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回<em>打败所有怪物所需的&nbsp;<strong>最少&nbsp;</strong>天数。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> power = [3,1,4]\n",
    "<strong>输出:</strong> 4\n",
    "<strong>解释:</strong> 打败所有怪物的最佳方法是:\n",
    "- 第 1 天: 获得 1 点法力值，现在总共拥有 1 点法力值。用尽所有法力值击杀第 2 个怪物。\n",
    "- 第 2 天: 获得 2 点法力值，现在总共拥有 2 点法力值。\n",
    "- 第 3 天: 获得 2 点法力值，现在总共拥有 4 点法力值。用尽所有法力值击杀第 3 个怪物。\n",
    "- 第 4 天: 获得 3 点法力值，现在总共拥有 3 点法力值。 用尽所有法力值击杀第 1 个怪物。\n",
    "可以证明，4 天是最少需要的天数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> power = [1,1,4]\n",
    "<strong>输出:</strong> 4\n",
    "<strong>解释:</strong> 打败所有怪物的最佳方法是:\n",
    "- 第 1 天: 获得 1 点法力值，现在总共拥有 1 点法力值。用尽所有法力值击杀第 1 个怪物。\n",
    "- 第 2 天: 获得 2 点法力值，现在总共拥有 2 点法力值。用尽所有法力值击杀第 2 个怪物。\n",
    "- 第 3 天: 获得 3 点法力值，现在总共拥有 3 点法力值。\n",
    "- 第 4 天: 获得 3 点法力值，现在总共拥有 6 点法力值。用尽所有法力值击杀第 3 个怪物。\n",
    "可以证明，4 天是最少需要的天数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> power = [1,2,4,9]\n",
    "<strong>输出:</strong> 6\n",
    "<strong>解释:</strong> 打败所有怪物的最佳方法是:\n",
    "- 第 1 天: 获得 1 点法力值，现在总共拥有 1 点法力值。用尽所有法力值击杀第 1 个怪物\n",
    "- 第 2 天: 获得 2 点法力值，现在总共拥有 2 点法力值。用尽所有法力值击杀第 2 个怪物。\n",
    "- 第 3 天: 获得 3 点法力值，现在总共拥有 3 点法力值。\n",
    "- 第 4 天: 获得 3 点法力值，现在总共拥有 6 点法力值。\n",
    "- 第 5 天: 获得 3 点法力值，现在总共拥有 9 点法力值。用尽所有法力值击杀第 4 个怪物。\n",
    "- 第 6 天: 获得 4 点法力值，现在总共拥有 4 点法力值。用尽所有法力值击杀第 3 个怪物。\n",
    "可以证明，6 天是最少需要的天数。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= power.length &lt;= 17</code></li>\n",
    "\t<li><code>1 &lt;= power[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-time-to-kill-all-monsters](https://leetcode.cn/problems/minimum-time-to-kill-all-monsters/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-time-to-kill-all-monsters](https://leetcode.cn/problems/minimum-time-to-kill-all-monsters/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,1,4]', '[1,1,4]', '[1,2,4,9]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "from math import ceil\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        power.sort()\n",
    "        N = len(power)\n",
    "        MAXP = power[-1]\n",
    "        queue = [(int(ceil(sum(power[i - 1] / i for i in range(1, N + 1)))), 0, 0, 0)]\n",
    "        current_min = {0: 0}\n",
    "        def _ceildiv(x, y):\n",
    "            return (x + y - 1) // y\n",
    "\n",
    "        while queue:\n",
    "            _, mask, selected, total = heappop(queue)\n",
    "            if mask == ((1 << N) - 1):\n",
    "                return total\n",
    "            if current_min[mask] < total:\n",
    "                continue\n",
    "            upper_bound = MAXP\n",
    "            last_try = 0\n",
    "            a = selected + 1\n",
    "            for j in range(N):\n",
    "                if not ((1 << j) & mask):\n",
    "                    if power[j] > upper_bound:\n",
    "                        break\n",
    "                    # 剪枝1：重复的数字只按照从前往后的顺序匹配\n",
    "                    if power[j] == last_try:\n",
    "                        continue\n",
    "                    last_try = power[j]\n",
    "                    next_total = total + _ceildiv(power[j], a)\n",
    "                    next_mask = (mask | (1 << j))\n",
    "                    # 剪枝2：选中相同集合时只保留最佳答案（类似状态压缩DP）\n",
    "                    if next_mask in current_min and current_min[next_mask] <= next_total:\n",
    "                        continue\n",
    "                    current_min[next_mask] = next_total\n",
    "                    # A*估值函数：利用sum(ceil(a/b)) >= ceil(sum(a/b))\n",
    "                    estimate = next_total + \\\n",
    "                        int(ceil(sum(p / k for p, k in zip(\n",
    "                            (p for l, p in enumerate(power)\n",
    "                                if not ((1 << l) & next_mask)),\n",
    "                            range(a + 1, N + 1)\n",
    "                        ))))\n",
    "                    heappush(queue, (estimate, next_mask, selected + 1, next_total))\n",
    "                    # 剪枝3：需要尝试的数值可以被限定在一个较小的范围内\n",
    "                    current_upper = 0\n",
    "                    m = power[j]\n",
    "                    for b in range(a + 1, N + 1):\n",
    "                        est_upper = (_ceildiv(m, a) * a * b - a * (m+1)) // (b-a)\n",
    "                        if est_upper <= current_upper:\n",
    "                            break\n",
    "                        real_upper = ((_ceildiv(m, a) - _ceildiv(m, b)) * a * b - a) // (b - a)\n",
    "                        current_upper = max(current_upper, real_upper)\n",
    "                        if current_upper >= upper_bound:\n",
    "                            break\n",
    "                    upper_bound = min(current_upper, upper_bound)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappop, heappush\n",
    "from math import ceil\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        power.sort()\n",
    "        N = len(power)\n",
    "        MAXP = power[-1]\n",
    "        queue = [(int(ceil(sum(power[i - 1] / i for i in range(1, N + 1)))), 0, 0, 0)]\n",
    "        current_min = {0: 0}\n",
    "\n",
    "        def _ceildiv(x, y):\n",
    "            return (x + y - 1) // y\n",
    "\n",
    "        while queue:\n",
    "            _, mask, selected, total = heappop(queue)\n",
    "            if mask == ((1 << N) - 1):\n",
    "                return total\n",
    "            if current_min[mask] < total:\n",
    "                continue\n",
    "\n",
    "            upper_bound = MAXP\n",
    "            last_try = 0\n",
    "            a = selected + 1\n",
    "            for j in range(N):\n",
    "                if not ((1 << j) & mask):\n",
    "                    if power[j] > upper_bound:\n",
    "                        break\n",
    "                    if power[j] == last_try:\n",
    "                        continue\n",
    "                    last_try = power[j]\n",
    "\n",
    "                    next_total = total + _ceildiv(power[j], a)\n",
    "                    next_mask = (mask | (1 << j))\n",
    "                    if next_mask in current_min and current_min[next_mask] <= next_total:\n",
    "                        continue\n",
    "\n",
    "                    current_min[next_mask] = next_total\n",
    "                    estimate = next_total + int(ceil(sum(p / k for p, k in zip(\n",
    "                        (p for l, p in enumerate(power) if not ((1 << l) & next_mask)),\n",
    "                        range(a + 1, N + 1)\n",
    "                    ))))\n",
    "                    heappush(queue, (estimate, next_mask, selected + 1, next_total))\n",
    "                    \n",
    "                    current_upper = 0\n",
    "                    m = power[j]\n",
    "                    for b in range(a + 1, N + 1):\n",
    "                        est_upper = (_ceildiv(m, a) * a * b - a * (m+1)) // (b-a)\n",
    "                        if est_upper <= current_upper:\n",
    "                            break\n",
    "                        real_upper = ((_ceildiv(m, a) - _ceildiv(m, b)) * a * b - a) // (b - a)\n",
    "                        current_upper = max(current_upper, real_upper)\n",
    "                        if current_upper >= upper_bound:\n",
    "                            break\n",
    "                    upper_bound = min(current_upper, upper_bound)\n",
    "\n",
    "# 示例\n",
    "s = Solution()\n",
    "print(s.minimumTime([3, 5, 7]))  # 输出应该是天数\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "from math import ceil\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        power.sort()\n",
    "        N = len(power)\n",
    "        MAXP = power[-1]\n",
    "        queue = [(int(ceil(sum(power[i - 1] / i for i in range(1, N + 1)))), 0, 0, 0)]\n",
    "        current_min = {0: 0}\n",
    "        def _ceildiv(x, y):\n",
    "            return (x + y - 1) // y\n",
    "\n",
    "        while queue:\n",
    "            _, mask, selected, total = heappop(queue)\n",
    "            if mask == ((1 << N) - 1):\n",
    "                return total\n",
    "            if current_min[mask] < total:\n",
    "                continue\n",
    "            upper_bound = MAXP\n",
    "            last_try = 0\n",
    "            a = selected + 1\n",
    "            for j in range(N):\n",
    "                if not ((1 << j) & mask):\n",
    "                    if power[j] > upper_bound:\n",
    "                        break\n",
    "                    # 剪枝1：重复的数字只按照从前往后的顺序匹配\n",
    "                    if power[j] == last_try:\n",
    "                        continue\n",
    "                    last_try = power[j]\n",
    "                    next_total = total + _ceildiv(power[j], a)\n",
    "                    next_mask = (mask | (1 << j))\n",
    "                    # 剪枝2：选中相同集合时只保留最佳答案（类似状态压缩DP）\n",
    "                    if next_mask in current_min and current_min[next_mask] <= next_total:\n",
    "                        continue\n",
    "                    current_min[next_mask] = next_total\n",
    "                    # A*估值函数：利用sum(ceil(a/b)) >= ceil(sum(a/b))\n",
    "                    estimate = next_total + \\\n",
    "                        int(ceil(sum(p / k for p, k in zip(\n",
    "                            (p for l, p in enumerate(power)\n",
    "                                if not ((1 << l) & next_mask)),\n",
    "                            range(a + 1, N + 1)\n",
    "                        ))))\n",
    "                    heappush(queue, (estimate, next_mask, selected + 1, next_total))\n",
    "                    # 剪枝3：需要尝试的数值可以被限定在一个较小的范围内\n",
    "                    current_upper = 0\n",
    "                    m = power[j]\n",
    "                    for b in range(a + 1, N + 1):\n",
    "                        est_upper = (_ceildiv(m, a) * a * b - a * (m+1)) // (b-a)\n",
    "                        if est_upper <= current_upper:\n",
    "                            break\n",
    "                        real_upper = ((_ceildiv(m, a) - _ceildiv(m, b)) * a * b - a) // (b - a)\n",
    "                        current_upper = max(current_upper, real_upper)\n",
    "                        if current_upper >= upper_bound:\n",
    "                            break\n",
    "                    upper_bound = min(current_upper, upper_bound)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        power = sorted(power)\n",
    "        gain = 1\n",
    "\n",
    "        n = len(power)\n",
    "        x = power[0]\n",
    "        visited = [0]*n\n",
    "        visited[0] = 1\n",
    "\n",
    "        m = n-1\n",
    "        full_mask = 1<<m\n",
    "        dp = [float(\"inf\")]*(1<<m)\n",
    "        dp[0] = power[0]\n",
    "        \n",
    "        for mask in range(1,full_mask):\n",
    "            for j in range(m):\n",
    "                if mask & (1<<j)==0:\n",
    "                    continue \n",
    "                count = mask.bit_count()\n",
    "                gain = 1+count\n",
    "                x = (power[j+1]//gain)+1 if power[j+1]%gain else power[j+1]//gain\n",
    "                dp[mask] = min(dp[mask], dp[mask ^(1<<j)]+x)\n",
    "        \n",
    "        return dp[full_mask-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        n=len(power)\n",
    "        dp=[0]*(1<<n)\n",
    "        for i in range(1,1<<n):\n",
    "            c=0\n",
    "            tp=[]\n",
    "            for j in range(n):\n",
    "                if i&(1<<j):\n",
    "                    c+=1\n",
    "                    tmp=i^(1<<j)\n",
    "                    tp.append([j,tmp])\n",
    "            dp[i]=min(dp[tmp]+math.ceil(power[j]/c) for j,tmp in tp)\n",
    "        #print(dp)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        n = len(power)\n",
    "        dp = [float('inf') ] *(1 << n)\n",
    "        dp[0] = 0 \n",
    "        def gain(x):\n",
    "            g = 1\n",
    "            for i in range(n):\n",
    "                if (x >> i) & 1:\n",
    "                    g+=1\n",
    "            return g \n",
    "\n",
    "        for i in range(1<<n):\n",
    "            g = gain(i)\n",
    "            for j in range(n):\n",
    "                if (i >> j) & 1 == 0:\n",
    "                    dp[i | (1 << j)] = min(dp[i | (1 << j)], dp[i]+(power[j] + g - 1)//g)\n",
    "        \n",
    "        return dp[(1 << n) - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        \n",
    "        start_gain = 1\n",
    "        n = len(power)\n",
    "        dp = [10**11]*(1<<n)\n",
    "        dp[0] = 0\n",
    "        for mask in range(1<<n):\n",
    "            gain = start_gain-1\n",
    "            for i in range(17):\n",
    "                if (mask>>i) & 1:\n",
    "                    gain += 1\n",
    "            for i in range(17):\n",
    "                if (mask>>i) & 1:\n",
    "                    dp[mask] = min(dp[mask],dp[mask - (1<<i )] + ( power[i] + gain - 1) //gain ) \n",
    "            \n",
    "        return dp[-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        powers = power.copy()\n",
    "        power = []\n",
    "        ans = 0\n",
    "        for p in powers:\n",
    "            if p==1:\n",
    "                ans += 1\n",
    "            else:\n",
    "                power.append(p)\n",
    "        start_gain = 0\n",
    "        if ans :\n",
    "            powers = power.copy()\n",
    "            power = []\n",
    "            for p in powers:\n",
    "                if p==2:\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    power.append(p)\n",
    "            start_gain = ans + 1\n",
    "        else:\n",
    "            powers = power.copy()\n",
    "            power = []\n",
    "            for p in powers:\n",
    "                if p==2:\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    power.append(p)\n",
    "            start_gain = ans + 1 \n",
    "             \n",
    "            if ans:\n",
    "                ans += 1\n",
    "           \n",
    "\n",
    "        \n",
    "        n = len(power)\n",
    "        dp = [10**11]*(1<<n)\n",
    "        dp[0] = 0\n",
    "        for mask in range(1<<n):\n",
    "            gain = start_gain-1\n",
    "            for i in range(17):\n",
    "                if (mask>>i) & 1:\n",
    "                    gain += 1\n",
    "            for i in range(17):\n",
    "                if (mask>>i) & 1:\n",
    "                    dp[mask] = min(dp[mask],dp[mask - (1<<i )] + ( power[i] + gain - 1) //gain ) \n",
    "            \n",
    "        return dp[-1] + ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        powers = power.copy()\n",
    "        power = []\n",
    "        ans = 0\n",
    "        for p in powers:\n",
    "            if p==1:\n",
    "                ans += 1\n",
    "            else:\n",
    "                power.append(p)\n",
    "\n",
    "        if ans :\n",
    "            powers = power.copy()\n",
    "            power = []\n",
    "            for p in powers:\n",
    "                if p==2:\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    power.append(p)\n",
    "\n",
    "\n",
    "        start_gain = ans + 1\n",
    "        n = len(power)\n",
    "        dp = [10**11]*(1<<n)\n",
    "        dp[0] = 0\n",
    "        for mask in range(1<<n):\n",
    "            gain = start_gain-1\n",
    "            for i in range(17):\n",
    "                if (mask>>i) & 1:\n",
    "                    gain += 1\n",
    "            for i in range(17):\n",
    "                if (mask>>i) & 1:\n",
    "                    dp[mask] = min(dp[mask],dp[mask - (1<<i )] + ( power[i] + gain - 1) //gain ) \n",
    "            \n",
    "        return dp[-1] + ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        n = len(power)\n",
    "        dp = [float('inf') for _ in range(1 << n)]\n",
    "        dp[0] = 0 \n",
    "        def gain(x):\n",
    "            g = 1\n",
    "            for i in range(n):\n",
    "                if (x >> i) & 1:\n",
    "                    g+=1\n",
    "            return g \n",
    "\n",
    "        for i in range(1<<n):\n",
    "            g = gain(i)\n",
    "            for j in range(n):\n",
    "                if (i >> j) & 1 == 0:\n",
    "                    dp[i | (1 << j)] = min(dp[i | (1 << j)], dp[i]+(power[j] + g - 1)//g)\n",
    "        \n",
    "        return dp[(1 << n) - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        n=len(power)\n",
    "        dp=[0]*(1<<n)\n",
    "        for i in range(1,1<<n):\n",
    "            c=0\n",
    "            tp=[]\n",
    "            for j in range(n):\n",
    "                if i&(1<<j):\n",
    "                    c+=1\n",
    "                    tmp=i^(1<<j)\n",
    "                    tp.append([j,tmp])\n",
    "            dp[i]=min(dp[tmp]+math.ceil(power[j]/c) for j,tmp in tp)\n",
    "        print(dp)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        n=len(power)\n",
    "        dp = [{} for j in range(n+1)]\n",
    "        dp[0][0]=0 \n",
    "\n",
    "        for cnt in range(1,n+1):\n",
    "            for i,mon in enumerate(power):\n",
    "                for olds in dp[cnt-1]:\n",
    "                    s=olds|1<<i\n",
    "                    if s==olds:\n",
    "                        continue\n",
    "                    dps=dp[cnt-1][olds]+(mon-1)//cnt+1\n",
    "\n",
    "                    if s not in dp[cnt] or dp[cnt][s]>dps:\n",
    "                        dp[cnt][s]=dps\n",
    "        \n",
    "        return dp[-1][(1<<n)-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumTime(self, power: List[int]) -> int:\r\n",
    "\r\n",
    "        dp = [{} for j in range(len(power)+1)]\r\n",
    "        dp[0][0]=0  #边界条件\r\n",
    "        for cur in range(1,len(power)+1): #遍历打怪数量\r\n",
    "            for j,choose in enumerate(power): # 遍历当前选择的怪物\r\n",
    "                for ls in dp[cur-1]: #遍历上一层的所有状态\r\n",
    "                    s = ls|(1<<j)\r\n",
    "                    if s==ls: #这说明当前这只怪物打过了，跳过\r\n",
    "                        continue\r\n",
    "                    dps = dp[cur-1][ls]+(choose-1)//cur+1 # 注意当前怪物需要天数不能直接用整除，但可以直接调math.ceil\r\n",
    "                    if s not in dp[cur] or dp[cur][s]>dps: # s首次出现或者找到一个更优值时更新\r\n",
    "                        dp[cur][s]=dps\r\n",
    "        \r\n",
    "        return dp[-1][(1<<(len(power)))-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "\n",
    "        dp = [{} for j in range(len(power)+1)]\n",
    "        dp[0][0]=0  #边界条件\n",
    "        for cur in range(1,len(power)+1): #遍历打怪数量\n",
    "            for j,choose in enumerate(power): # 遍历当前选择的怪物\n",
    "                for ls in dp[cur-1]: #遍历上一层的所有状态\n",
    "                    s = ls|(1<<j)\n",
    "                    if s==ls: #这说明当前这只怪物打过了，跳过\n",
    "                        continue\n",
    "                    dps = dp[cur-1][ls]+(choose-1)//cur+1 # 注意当前怪物需要天数不能直接用整除，但可以直接调math.ceil\n",
    "                    if s not in dp[cur] or dp[cur][s]>dps: # s首次出现或者找到一个更优值时更新\n",
    "                        dp[cur][s]=dps\n",
    "        \n",
    "        return dp[-1][(1<<(len(power)))-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        '''\n",
    "        打倒怪物的顺序会影响到最终的答案\n",
    "        所以，直接枚举所有怪物被击杀的顺序\n",
    "        f[i][mask]前i次击杀，击杀的怪物集合为mask\n",
    "        f[i][mask]=枚举第i次击杀了第j个怪物，f[i-1][mask^(1<<j)]+cnt[i][j]\n",
    "        cnt[i][j]预处理在每天获得gain点能量的情况下，击杀第j个怪物的最短耗时\n",
    "        cnt[i][j]=math.ceil(power[j]/i)\n",
    "        '''\n",
    "        n=len(power)\n",
    "        MX=1<<n\n",
    "        f=[[inf]*MX for _ in range(n+1)] #总共需要n次击杀  \n",
    "        f[0][0]=0\n",
    "        for i in range(n):\n",
    "            for j in range(1,MX):\n",
    "                if j.bit_count()!=i+1:\n",
    "                    continue\n",
    "                for bit in range(n):\n",
    "                    if j>>bit&1:\n",
    "                        f[i+1][j]=min(f[i+1][j],f[i][j^(1<<bit)]+math.ceil(power[bit]/(i+1)))\n",
    "        return f[n][MX-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        n = len(power)\n",
    "        @cache\n",
    "        def dfs(st):\n",
    "            k = st.bit_count()+1\n",
    "            if k==n+1:\n",
    "                return 0\n",
    "            res = inf\n",
    "            for i in range(n):\n",
    "                if not st&1<<i:\n",
    "                    res = min(res,(power[i]-1)//k+1+dfs(st|1<<i))\n",
    "            return res\n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        #状态压缩+记忆化搜索,1表示当前还未打败，0表示当前已打败\n",
    "        n=len(power)\n",
    "        @cache\n",
    "        def dfs(mask):\n",
    "            if mask==0: return 0\n",
    "            bit=n-mask.bit_count()   #0的个数\n",
    "            res=inf\n",
    "            for i in range(n):\n",
    "                if mask>>i&1:\n",
    "                    res=min(res,dfs(mask^(1<<i))+ceil(power[i]/(1+bit)))\n",
    "            return res\n",
    "        return dfs((1<<n)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        n = len(power)\n",
    "\n",
    "        @cache\n",
    "        def dfs(mask):\n",
    "            cnt = mask.bit_count()\n",
    "            if cnt == n:\n",
    "                return 0\n",
    "            \n",
    "            ans = inf\n",
    "            for i in range(n):\n",
    "                cur = 1 << i\n",
    "                if mask & cur:\n",
    "                    continue\n",
    "                ans = min(ans, dfs(mask | cur) + ceil(power[i] / (cnt + 1)))\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        #状态压缩+记忆化搜索,1表示当前还未打败，0表示当前已打败\n",
    "        n=len(power)\n",
    "        @cache\n",
    "        def dfs(mask):\n",
    "            if mask==0: return 0\n",
    "            bit=n-mask.bit_count()   #0的个数\n",
    "            res=inf\n",
    "            for i in range(n):\n",
    "                if mask>>i&1:\n",
    "                    res=min(res,dfs(mask^(1<<i))+ceil(power[i]/(1+bit)))\n",
    "            return res\n",
    "        return dfs((1<<n)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumTime(self, power: List[int]) -> int:\r\n",
    "        n = len(power)\r\n",
    "\r\n",
    "        @cache\r\n",
    "        def dfs(mask):\r\n",
    "            cnt = mask.bit_count()\r\n",
    "            if cnt == n:\r\n",
    "                return 0\r\n",
    "            \r\n",
    "            ans = inf\r\n",
    "            for i in range(n):\r\n",
    "                cur = 1 << i\r\n",
    "                if mask & cur:\r\n",
    "                    continue\r\n",
    "                ans = min(ans, dfs(mask | cur) + ceil(power[i] / (cnt + 1)))\r\n",
    "            return ans\r\n",
    "        \r\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        @cache\n",
    "        def mDFS(mask):\n",
    "            if mask == ed: return 0\n",
    "            gain = mask.bit_count() + 1\n",
    "            res = inf\n",
    "            for k, x in enumerate(power):\n",
    "                if mask >> k & 1: continue\n",
    "                res = min(res, mDFS(mask | (1 << k)) + (x + gain - 1) // gain)\n",
    "            return res\n",
    "\n",
    "        ed = (1 << len(power)) - 1\n",
    "        return mDFS(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        n = len(power)\n",
    "        @lru_cache(None)\n",
    "        def dfs(pos):\n",
    "            if pos == (1 << n) - 1:\n",
    "                return 0\n",
    "            res = float('inf')\n",
    "            k = bin(pos).count('1')\n",
    "            for i in range(n):\n",
    "                if pos & (1 << i) == 0:\n",
    "                    res = min(res, dfs(pos | (1 << i)) + ceil(power[i] / (k + 1)))\n",
    "            return res\n",
    "        return dfs(0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param power:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        max1 = max(power)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def get_min_time(pace, mana, fz):\n",
    "            if len(fz) == len(power):\n",
    "                return 0\n",
    "            if pace > 10 * max1:\n",
    "                return math.inf\n",
    "            v1 = math.inf\n",
    "\n",
    "            for i in range(len(power)):\n",
    "                if i not in fz:\n",
    "                    cur_val = power[i]\n",
    "                    gap = cur_val - pace\n",
    "                    v2 = math.ceil(max(0, gap)/mana) + get_min_time(0, mana+1, fz.union({i}))\n",
    "                    v1 = min(v1, v2)\n",
    "            #v1 = min(v1, 1 + get_min_time(pace+mana, mana, fz))\n",
    "            return v1\n",
    "\n",
    "\n",
    "\n",
    "        ret = get_min_time(0, 1, frozenset({}))\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param power:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        max1 = max(power)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def get_min_time(pace, mana, fz):\n",
    "            if len(fz) == len(power):\n",
    "                return 0\n",
    "            v1 = math.inf\n",
    "            for i in range(len(power)):\n",
    "                if i not in fz:\n",
    "                    cur_val = power[i]\n",
    "                    gap = cur_val - pace\n",
    "                    v2 = math.ceil(max(0, gap)/mana) + get_min_time(0, mana+1, fz.union({i}))\n",
    "                    v1 = min(v1, v2)\n",
    "            return v1\n",
    "\n",
    "        return get_min_time(0, 1, frozenset({}))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param power:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        max1 = max(power)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def get_min_time(pace, mana, fz):\n",
    "            if len(fz) == len(power):\n",
    "                return 0\n",
    "        \n",
    "            v1 = math.inf\n",
    "\n",
    "            for i in range(len(power)):\n",
    "                if i not in fz:\n",
    "                    cur_val = power[i]\n",
    "                    gap = cur_val - pace\n",
    "                    v2 = math.ceil(max(0, gap)/mana) + get_min_time(0, mana+1, fz.union({i}))\n",
    "                    v1 = min(v1, v2)\n",
    "            #v1 = min(v1, 1 + get_min_time(pace+mana, mana, fz))\n",
    "            return v1\n",
    "\n",
    "\n",
    "\n",
    "        ret = get_min_time(0, 1, frozenset({}))\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, power: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param power:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        max1 = max(power)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def get_min_time(pace, mana, fz):\n",
    "            if len(fz) == len(power):\n",
    "                return 0\n",
    "            if pace > max1 + 2 * mana:\n",
    "                return math.inf\n",
    "            v1 = math.inf\n",
    "\n",
    "            for i in range(len(power)):\n",
    "                if i not in fz:\n",
    "                    cur_val = power[i]\n",
    "                    gap = cur_val - pace\n",
    "                    v2 = math.ceil(max(0, gap)/mana) + get_min_time(0, mana+1, fz.union({i}))\n",
    "                    v1 = min(v1, v2)\n",
    "            #v1 = min(v1, 1 + get_min_time(pace+mana, mana, fz))\n",
    "            return v1\n",
    "\n",
    "\n",
    "\n",
    "        ret = get_min_time(0, 1, frozenset({}))\n",
    "        return ret\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
